package com.cskaoyan.javase.recursion._3exercise;

/**
 * @description: 汉诺塔问题
 * @author: wuguidong@cskaoyan.onaliyun.com
 **/

/**
 * 汉诺塔问题是经典的递归问题
 * 相传在古印度的圣庙中，有一种被称之为汉诺塔（也叫河内塔，Hanoi）的游戏
 * 简单来说：有三个塔1，2，3，塔1上有 N 个（N>1）穿孔圆盘，大盘在下，小盘在上
 * 要求按下列规则将所有圆盘移至塔3：
 * 	1，每次只能移动一个圆盘
 * 	2，大盘一定在小盘之下
 * 提示：可将圆盘临时置于塔2，也可以将塔1的圆盘重新移回塔1，但都必须遵循上述两条规则
 * 问：当塔1上有N（N>=1）个圆盘时，最少要移动多少次？（注意是最少）
 *
 * 移动过程:
 * 1. 当N = 1时，直接把盘子从塔1到塔3，仅需1步
 * 2. 当N=2时，先把小盘子移到塔2，再把大盘子移到塔3，最后把小盘子放入塔3，共3步
 * 3. 当N=3时，先把最小的盘子移到塔3，再把中间的盘子移到塔2
 *    - 然后把最小的盘子移到塔2，最大的盘子移到塔3
 *    - 随后最小的盘子移到塔1，中间的盘子移到塔3，最小的盘子移到塔3，共7步
 *
 * 以上总结规律:
 * 1.无论N等于多少,总有一步需要把最大的盘子移到塔3上去
 * 2.要想完成步骤一,必须把除了最大盘子外的所有盘子从塔1移到塔2上去
 * 3.完成步骤一后,必须把除了最大盘子外的所有盘子从塔2移到塔3上去
 *
 *
 * 假设一共至少需要f(N)步完成汉诺塔问题(N是盘子个数),
 * 所以汉诺塔问题的求解就可以分解成三个步骤:
 * 1.必须把除了最大盘子外的所有盘子从塔1移到塔2上去,这个过程需要借助塔3辅助,共需要f(N-1)步
 * 2.把最大的盘子从塔1到塔3,共需要1步
 * 3.必须把除了最大盘子外的所有盘子从塔2移到塔3上去,这个过程需要借助塔1辅助,共需要f(N-1)步
 *
 * 所以分解后的f(N) = f(N-1) + 1 + f(N-1),它就是递归当中的递归体
 * 递归的出口: f(1) = 1
 *
 * 已知f(N) = f(N-1) + 1 + f(N-1),求f(N)的通项公式
 * f(N) = 2f(N-1) + 1
 * f(N) + 1 = 2 (f(N-1) + 1)
 * f(N) + 1 / (f(N-1) + 1) = 2 这是等比数列的通项公式
 * f(N) + 1 = 2的n次方
 * f(N) = 2的n次方 - 1
 *
 */
public class Demo {
    public static void main(String[] args) {
        System.out.println(hanoi(100));
    }

    //求解汉诺塔问题
    public static long hanoi(int n) {
        //写递归的出口
        if (n == 1) return 1;
        return hanoi(n - 1) + 1 + hanoi(n - 1);
    }
}
